import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

//串联所有单词的子串；
//实例：
//输出：s="barfoofoobarthefoobarman"，word=["bar","foo","the"];
//输入：[6,9,12];
public class NM1 {
    public static List<Integer> fun(String s,String[] word) {
        //1.使用哈希表进行统计字符数组的的每个单词；
        Map<String, Integer> hash1 = new HashMap<>();
        for (String str : word){
            hash1.put(str, hash1.getOrDefault(str,0)+1);
        }
        //2.进行相关变量的设置；
        int len=word[0].length();//字符数组中每个单词的个数；
        int m= word.length;//字符数组的长度；
        List<Integer> ret=new ArrayList<>();//进行返回结果变量的正确设置；
        //3.进行滑动窗口方法的进行；
        //注意：此题进行滑动窗口的次数，为单词的长度的个数；
        for(int i=0;i<len;i++){
            Map<String,Integer> hash2=new HashMap<>();
            //进行len次的滑动窗口；
            for(int left=i,right=i,count=0;right+len<=s.length();right+=len){
                //进窗口+count的维护；(进窗口后进行维护count);
                String in=s.substring(right,right+len);//进行对s字符串中子串规定长度进行正确截取；
                hash2.put(in,hash2.getOrDefault(in,0)+1);
                if(hash2.get(in)<=hash1.getOrDefault(in,0)){
                    count++;
                }
                //判断；
                if(right-left+1>len*m){
                    //出窗口+维护count;
                    String out=s.substring(left,left+len);
                    if(hash2.get(out)<=hash1.getOrDefault(out,0)){
                        count--;
                    }
                    //进行出哈希表；
                    hash2.put(out, hash2.get(out)-1);
                    left=left+len;
                }
                //进行更新结果;
                if(count==m) {
                    ret.add(left);
                }
            }
        }
        return ret;
    }
    public static void main(String[] args){
        String s="barfoofoobarthefoobarman";
        String[] word={"bar","foo","the"};
        List<Integer> ret=fun(s,word);
        System.out.println(ret);
    }
}
